package TreeNode;

import static TreeNode.RedBlackTree.Color.BLACK;
import static TreeNode.RedBlackTree.Color.RED;

public class RedBlackTree {

    enum Color {
        RED,BLACK;
    }

    private TreeNode root;

    private static class TreeNode {
        int key;
        Object value;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        Color color = RED;

        //构造方法
        public TreeNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public TreeNode(int key, Object value, TreeNode left, TreeNode right, TreeNode parent) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }

        //判断是否为左孩子
         public boolean isLeftChild() {
             return parent != null && parent.left == this;
         }

         //获取叔叔节点
         public TreeNode uncle() {
             if (this.parent == null || this.parent.parent == null) {
                 return null;
             }
             if (this.isLeftChild()) {
                 return this.parent.parent.right;
             } else {
                 return this.parent.parent.left;
             }
         }

         //获取兄弟节点
         public TreeNode brother() {
             if (this.parent == null) {
                 return null;
             }
             if (this.isLeftChild()) {
                 return this.parent.right;
             }else {
                 return this.parent.left;
             }
         }


    }

    //判断是否为红色节点
    private boolean isRed(TreeNode node) {
        return node != null && node.color == RED;
    }

    //判断是否为黑色节点
    private  boolean isBlack(TreeNode node) {
        return node == null || node.color == BLACK;
    }

    //右旋
    //1.考虑旋转后节点的维护parent 2.重新与上一个节点建立联系
    private void rightRotate(TreeNode node) {
        TreeNode parent = node.parent;
        TreeNode nodeLeft = node.left;
        TreeNode nodeLeftRight = nodeLeft.right;
        if (nodeLeftRight != null) {
            nodeLeftRight.parent = node;
        }
        nodeLeft.right = node;
        nodeLeft.parent = parent;
        node.left = nodeLeftRight;
        node.parent = nodeLeft;
        if (parent == null) {
            root = nodeLeft;
        } else if (parent.left == node) {
            parent.left = nodeLeft;
        }else {
            parent.right = nodeLeft;
        }

    }

    //左旋
    //1.考虑旋转后节点的维护parent 2.重新与上一个节点建立联系
    private void leftRotate(TreeNode node) {
        TreeNode parent = node.parent;
        TreeNode nodeRight = node.right;
        TreeNode nodeRightLeft = nodeRight.left;
        if (nodeRightLeft != null) {
            nodeRightLeft.parent = node;
        }
        nodeRight.left = node;
        nodeRight.parent = parent;
        node.right = nodeRightLeft;
        node.parent = nodeRight;
        //2.重新与上一个节点建立联系
        if (parent == null) {
            root = nodeRight;
        } else if (parent.left == node) {
            parent.left = nodeRight;
        }else {
            parent.right = nodeRight;
        }

    }

    //更新、增添节点
    //正常更新、删除，遇到红红不平衡则需要进行调整
    public void put (int key, Object value) {
        TreeNode p = root;
        TreeNode parent = null;
        while (p != null) {
            parent = p;
            if (p.key > key) {
                p = p.left;
            }else if (p.key < key) {
                p = p.right;
            }else {
                p.value = value;
                return;
            }
        }
        TreeNode node = new TreeNode(key,value);
        if (parent == null) {
            root = node;
        }else {
            if (node.key > parent.key) {
                parent.right = node;

            }else {
                parent.left = node;

            }
            node.parent = parent;
        }
        //可能会发生红红不平衡，则需要调整
        fixRedRed(node);

    }
    //调整红红不平衡

    private void fixRedRed(TreeNode node) {
        //case1: 插入节点为根节点，将根节点变黑
        if(node == root) {
            node.color = BLACK;
            return;
        }
        if (isBlack(node.parent)) {
            //case2:插入节点的父亲若为黑，树的红黑性质不变，无需调整
            //无需调整
            return;
        }
        // 插入节点的父亲为红色，触发红红相邻
        //case3:叔叔为红色
        TreeNode parent = node.parent;
        TreeNode grandparent = parent.parent;
        TreeNode uncle = node.uncle();
        if (isRed(uncle)) {
            //进行变色处理即可
            //将其父亲、叔叔变为黑色，爷爷变为红色
            //若爷爷触发了红红，则继续递归调用该函数
            parent.color = BLACK;
            uncle.color = BLACK;
            grandparent.color = RED;
            fixRedRed(grandparent);
            return;
        }
        
        //case4:叔叔为黑色
        //该父亲为左孩子，该插入点也为左孩子，则触发 ll
        if (parent.isLeftChild() && node.isLeftChild()) {
            //先将父亲变为黑色、爷爷变为红色，再右旋转
            parent.color = BLACK;
            grandparent.color = RED;
            rightRotate(grandparent);
        }else if (parent.isLeftChild()) {
            //该插入节点为右孩子、该父亲为左孩子，则触发 lr
            //先左旋变为 ll 情况
            leftRotate(parent);
            node.color = BLACK;
            grandparent.color = RED;
            rightRotate(grandparent);
        } else if (!node.isLeftChild()) {
            //插入节点为右孩子、父亲节点也为右孩子 rr
            parent.color = BLACK;
            grandparent.color = RED;
            leftRotate(grandparent);
        }else {
            //插入节点为左孩子、父亲节点为右孩子 rl
            rightRotate(parent);
            node.color = BLACK;
            grandparent.color = RED;
            leftRotate(grandparent);

        }
    }

    //查找删除节点
    private TreeNode findDelete(int key) {
        TreeNode p = root;
        while(p != null) {
            if (p.key > key) {
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            }else {
                return p;
            }
        }
        //若没有找到则返回null
        return null;
    }

    //查找剩余节点
    private TreeNode findReplaced(TreeNode deleted) {
        //没有孩子的情况:
        if (deleted.left == null && deleted.right == null) {
            return null;
        }
        if (deleted.left == null) {
            return deleted.right;
        }
        if (deleted.right == null) {
            return deleted.left;
        }

        //有两个孩子的情况,找后继节点即可
        TreeNode p = deleted.right;
        while(p.left != null) {
            p = p.left;
        }
        return p;
    }

    //删除节点
    //正常删除节点，遇到黑黑不平衡则需要进行调整
    public void remove(int key) {
        TreeNode delete = findDelete(key);
        if (delete == null) {
            return;
        }
        doRemove(delete);

    }

    private void doRemove(TreeNode deleted) {
        TreeNode replaced = findReplaced(deleted);
        TreeNode parent = deleted.parent;
        //没有孩子的情况:
        if (replaced == null) {
            //删除的节点为根节点情况下:
            if (deleted == root) {
                root = null;
                return;
            }else {
                if (isRed(deleted)) {
                    //无需任何操作
                }else {
                    //触发黑黑不平衡，需要进行复杂的操作
                    fixBlackBlack(deleted);
                }
                if (deleted.isLeftChild()) {
                    parent.left = null;
                }else {
                    parent.right = null;
                }
                deleted.parent = null;
            }
            return;
        }
        //有一个孩子的情况
        if (deleted.left == null || deleted.right == null) {
            if (deleted == root) {
                root.key = replaced.key;
                root.value = replaced.value;
                root.left = root.right = null;
            }else {
                if (deleted.isLeftChild()) {
                    parent.left = replaced;
                } else {
                    parent.right = replaced;
                }
                replaced.parent = parent;
                deleted.left = deleted.right = deleted.parent = null;

                if (isRed(replaced) && isBlack(deleted)) {
                    //却少一个黑色，则将替换的节点换为红色即可
                    replaced.color = BLACK;
                }else {
                    //遇到黑黑不平衡情况，则需要进行复杂调整
                    fixBlackBlack(replaced);
                }
            }
            return;
        }
        //有两个孩子的情况,需要将用到李代桃僵技巧
        int key = deleted.key;
        deleted.key = replaced.key;
        replaced.key = key;

        Object value = deleted.value;
        deleted.value = replaced.value;
        replaced.value = value;
        doRemove(replaced);

    }
    private void fixBlackBlack(TreeNode node) {
        if (node == root) {
            return;
        }
        TreeNode parent = node.parent;
        TreeNode brother = node.brother();

        if (isRed(node.brother())) {
            //先进行旋转调整，再换色暂时达到平衡
            if (brother.isLeftChild()) {
                rightRotate(parent);
            }else {
                leftRotate(parent);
            }
            parent.color = RED;
            brother.color = BLACK;
            fixBlackBlack(node);
            return;
        }
        //两个侄子都为黑色
        if (brother == null) {
            fixBlackBlack(parent);
        }else {
            //case 4 兄弟是黑色，两个侄子也是黑色
            if (isBlack(brother.left) && isBlack(brother.right)) {
                brother.color = RED;
                if (isRed(parent)) {
                    parent.color = BLACK;
                }else {
                    fixBlackBlack(parent);
                }
            }

            //case 5 兄弟是黑色，侄子有红色
            else {
                //其中某一个侄子不为黑色
                //兄弟为左孩子、侄子为左孩子，触发 ll
                if (brother.isLeftChild() && isRed(brother.left)) {
                    rightRotate(parent);
                    brother.left.color = BLACK;
                    brother.color = parent.color;
                    parent.color = BLACK;
                } else if (brother.isLeftChild() && isRed(brother.right)) {
                    //兄弟为左孩子、侄子为右孩子，先触发 lr
                    //需要将 lr 转变为 ll 情况再处理
                    brother.right.color = parent.color;
                    leftRotate(brother);
                    rightRotate(parent);
                    parent.color = BLACK;
                } else if ( !brother.isLeftChild() && isRed(brother.right)) {
                    //兄弟为右孩子，侄子为右孩子，触发 rr
                    leftRotate(parent);
                    brother.right.color = BLACK;
                    brother.color = parent.color;
                    parent.color = BLACK;
                }else {
                    //最后一种情况兄弟为右孩子、侄子为左孩子，触发 rl
                    //需要将 rl 转变为 rr 情况再处理
                    brother.left.color = parent.color;
                    rightRotate(brother);
                    leftRotate(parent);
                    parent.color = BLACK;

                }
            }
        }

    }

}
